The present invention relates generally to buffer management and, more particularly, to an improved buffer management scheme employing dynamic thresholds.
Switch architectures use buffering mechanisms to accommodate packets whose service has been delayed due to contention for bandwidth or temporary congestion within the switch. Shared buffer memory switches are popular for their efficient buffer utilization. By sharing the buffer, for instance, among all output ports, and taking advantage of the statistical multiplexing on input traffic, shared-memory switches are able to achieve the same packet delay and loss performance with a smaller pool of buffers per port when compared with switches of other types. Such a reduction in buffer size is even more significant for bursty traffic and non-uniform traffic load at the switch ports. Thus, shared-memory switches have become very popular, since they can achieve a given loss probability requirement with the smallest amount of total memory.
However, as is well known, management and control of such a shared resource is a challenging task because of the conflicting objectives of maximizing buffer utilization and increasing the degree of statistical multiplexing, on one hand, and providing heterogeneous loss requirements and isolation to connections admitted into the system, on the other hand. Shared-memory switches without good buffer management procedures may not perform well under overload conditions, especially in regard to fairness. The statistical sharing of the buffer memory introduces the possibility of a small group of output ports hogging most of the memory, preventing packets destined for less utilized ports from gaining their fair shares of memory or even blocked completely.
One conventional solution to the above-stated problems is to set some restrictions on the amount of buffering a port can use (e.g., each queue has a threshold for the maximum number of buffers it can access, each queue is guaranteed a minimum number of buffers, etc.) A number of threshold-setting methods have been proposed for buffer management. These methods can be broadly categorized as static threshold methods (e.g., see G. J. Foschini, and B. Gopinath, xe2x80x9cSharing Memory Optimally,xe2x80x9d IEEE Trans. Communications, Vol. 3, March, 1983, pp. 352-360; F. Kamoun and L. Kleinrock, xe2x80x9cAnalysis of Shared Finite Storage in a Computer Network ode Environment under General Traffic Conditions,xe2x80x9d IEEE Trans. Communications, Vol. 28, July, 1980, pp. 992-1003; and G. Latouche, xe2x80x9cExponential Servers Sharing a Finite Storage: Comparison of Space Allocation Policies,xe2x80x9d IEEE Trans. Communications, Vol. 28, June, 1980, pp. 992-1003), and dynamic threshold methods (e.g., see A. K. Choudhury and E. L. Hahne, xe2x80x9cDynamic Queue Length Thresholds in a Shared Memory ATM Switch,xe2x80x9d Proc. IEEE INFOCOMxe2x80x2 96, Vol. 2, March, 1996, pp. 679-687; and R. Fan, A. Ishii, B. Mark, G. Ramamurthy, and Q. Ren, xe2x80x9cAn Optimal Buffer Management Scheme with Dynamic Thresholds,xe2x80x9d Proc. IEEE GLOBECOMxe2x80x2 99, December, 1999, pp. 631-637).
In a static threshold method, each queue is only allowed to grow up to a maximum length which is statically defined. Arriving packets destined to a queue whose length is equal to their threshold are discarded. With different settings of thresholds, the static threshold method varies from complete sharing (e.g., the individual threshold is set to full buffer capacity to achieve maximal utilization but no fairness among different ports) to complete partitioning (e.g., buffer capacity is completely partitioned to ensure fairness among different ports but could lead to least usage efficiency). Usually a good static threshold scheme has to take a good compromise between efficiency and fairness of buffer sharing. If the sum of the thresholds is close or equal to the total buffer size, static thresholding becomes very restrictive in the use of the available buffers, and results in low buffer utilization (the special case where the sum of the thresholds adds up to the total buffer size is referred to as complete partitioning). On the other hand, if the sum of the thresholds is much larger than the total buffer size, sharing is achieved, but the scheme does not provide minimum allocations and suffers from potential starvation. A variation of this scheme, referred to as static thresholding with minimum allocations, divides the total buffer space in two portions and implements complete partitioning in one of them to guarantee a minimum allocation. Still, however, because of the static nature of the scheme, the tradeoff between sharing and isolation that can be achieved may not be optimal.
In a dynamic threshold method, buffer thresholds are dynamically adjusted according to the changing traffic load. A dynamic threshold method intends to allow congested queues to gain access to buffers not utilized by lightly loaded queues as long as their queues do not exceed their fair share of the memory (i.e., the dynamic threshold). Therefore, a good dynamic threshold scheme should improve the overall switch buffer utilization while ensuring fair sharing of buffer memory among different queues. In general, dynamic threshold schemes require more processing and are more appropriate for buffer management of queues where traffic load may fluctuate substantially (although only lasting for a short time span).
Despite the above-described benefits of both static threshold methods and dynamic threshold methods, merely using an efficient and fair buffer allocation scheme in a shared-memory architecture, without appropriate queue management, does not necessarily lead to improved performance. That is, some form of active queue management is needed even for routers that use efficient dynamic buffer allocation mechanisms. This is because dynamic buffer allocation algorithms by themselves do nothing to control the overall queue size of individual queues (i.e., there is no direct control on the lengths of the individual queues). For example, while dynamic buffer allocation mechanisms can allocate buffer memory efficiently and fairly among output ports, fair buffer allocation does not necessarily result in efficient and fair buffer usage, particularly for transmission control protocol (TCP) (e.g., see V. Jacobson, xe2x80x9cCongestion Avoidance and Control,xe2x80x9d Proc. ACM SIGCOMMxe2x80x2 88, 1988, pp. 314-329; and W. Stevens, xe2x80x9cTCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms,xe2x80x9d IETF RFC 2001, January, 1997). Thus, active queue management is needed to control the overall queue sizes so that arriving bursts can be accommodated without dropping packets unnecessarily (e.g., see B. Braden et al., xe2x80x9cRecommendation on Queue Management and Congestion Avoidance in the Internet,xe2x80x9d IETF RFC 2309, April, 1998; and S. Floyd and V. Jacobson, xe2x80x9cRandom Early Detection Gateways for Congestion Avoidance,xe2x80x9d IEEE/ACM Trans. Networking, Vol. 1, No. 4, August, 1993, pp. 397-413).
The basic idea behind active queue management schemes such as, for example, random early detection (RED), is to detect incipient congestion early and to convey congestion notification to the end-systems, allowing them to reduce their transmission rates before queue overflow and sustained packet loss occur. In addition, active queue management can be used to control the queue sizes for each individual port so that they do not experience unnecessarily high delays.
In the basic RED scheme, as well as in improvements thereto such as described in the above-referenced related U.S. patent application Ser. No. 09/455,445, filed Dec. 6, 1999, a queue length average is maintained and used, along with a number of queue thresholds, to detect congestion. If congestion is detected, incoming packets are dropped (or marked, e.g., see S. Floyd, xe2x80x9cTCP and Explicit Congestion Notificationxe2x80x9d, ACM Computer Communication Review, Vol. 24, No. 5, October, 1994, pp. 10-23) in a random probabilistic manner where the probability is a function of recent buffer fill history. The objective is to provide a more equitable distribution of packet loss among the different flows, avoid the synchronization of flows, and, at the same time, improve the utilization of the network.
Despite the benefits associated with the above-described basic and improved RED schemes, there are still shortcomings associated therewith. One such shortcoming is in the setting of the queue thresholds. That is, the setting of the queue thresholds in a RED scheme in a shared-memory architecture can be problematic because the required thresholds for good and fair buffer sharing among switch ports is dependent on the number of TCP connections using the buffer. Thus, there remains a need for enhancing the effectiveness of a RED scheme in a shared-memory architecture by dynamically changing the threshold settings as the number of connections (and the system load) changes.
According to the present invention, an improved buffer management scheme is provided wherein the buffer is shared among a plurality of packet queues. In a preferred embodiment, the improvement is realized by dynamically computing a common queue threshold value based upon the aggregate size of the plurality of packet queues and a predetermined buffer threshold value. The common queue threshold value is then used to manage the size of each of the plurality of packet queues and thereby manage the buffer.
In accordance with other aspects of the present invention, the improvement further comprises recomputing the common queue threshold value at predetermined time intervals.
In accordance with further aspects of the present invention, the improvement further comprises computing a packet drop probability for each of the plurality of packet queues based upon the common queue threshold value.
In accordance with still further aspects of the present invention, a predetermined increment threshold value is used to compute the common queue threshold value. That is, the computed common queue threshold value is the smaller of the sum of a current common queue threshold value and the predetermined increment threshold value or the predetermined buffer threshold value if the aggregate size of the plurality of packet queues is less than the predetermined buffer threshold value. Alternatively, the computed common queue threshold value is the larger of the difference of a current common queue threshold value and the predetermined increment threshold value or a predetermined minimum queue threshold value if the aggregate size of the plurality of packet queues is greater than or equal to the predetermined buffer threshold value.
The present invention will now be described in more detail with reference to exemplary embodiments thereof as shown in the appended drawings. While the present invention is described below with reference to preferred embodiments, it should be understood that the present invention is not limited thereto. Those of ordinary skill in the art having access to the teachings herein will recognize additional implementations, modifications, and embodiments, as well as other fields of use, which are within the scope of the present invention as disclosed and claimed herein, and with respect to which the present invention could be of significant utility.